
    /*  图像渲染

    class Solution {
        //设置偏移量 上下左右四个坐标
        int[] dx = { 0, 0, 1, -1 };
        int[] dy = { 1, -1, 0, 0 };

        public int[][] floodFill(int[][] image, int sr, int sc, int color) {
            // 记录初始颜色
            int prev = image[sr][sc];

            // 初始颜色和目标颜色相同，则直接返回原图
            if (prev == color)
                return image;

            int m = image.length;
            int n = image[0].length;
            // 构造一个队列，先把起始点放进去
            Queue<int[]> q = new LinkedList<>();
            q.offer(new int[] { sr, sc });
            // 当队列不为空
            while (!q.isEmpty()) {
                int[] t = q.poll();
                int a = t[0], b = t[1];
                // 改变颜色
                image[a][b] = color;
                // 遍历四个方向
                for (int i = 0; i < 4; i++) {
                    int x = a + dx[i];
                    int y = b + dy[i];
                    // 防止越界 并且上下左右如果有跟原来的颜色相同 加入队列并修改颜色
                    if (x >= 0 && x < m && y >= 0 && y < n && image[x][y] == prev) {
                        q.offer(new int[] { x, y });
                    }
                }
            }
            return image;
        }
    }


     */

    /* 岛屿数量

     */

    /* 路径总和 II
    class Solution {
        List<List<Integer>> ret;
        List<Integer> path;

        public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
            ret = new ArrayList<>();
            path = new ArrayList<>();
            dfs(root, targetSum);
            return ret;
        }

        void dfs(TreeNode root, int targetSum) {
            if (root == null)
                return;
            targetSum -= root.val;
            path.add(root.val);
            if (root.left == null && root.right == null) {
                if (0 == targetSum) {
                    ret.add(new ArrayList<>(path));
                }
            }
            dfs(root.left, targetSum);
            dfs(root.right, targetSum);
            path.remove(path.size() - 1);
        }
    }
     */

    /* 路径总和
    class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null) return false;
        targetSum -= root.val;
        if(root.left == null && root.right == null) {
            return targetSum == 0;
        }
        return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum) ;
    }
}

     */

    /* 峰与谷
    class Solution {
    public void wiggleSort(int[] nums) {
        for(int i = 1; i < nums.length ; i++) {
            //奇数是谷 偶数是峰
            if((i % 2 == 0 && nums[i] < nums[i-1] )
            ||  (i % 2 == 1 && nums[i] > nums[i-1])) {
                int tmp = nums[i];
                nums[i] = nums[i-1];
                nums[i-1] = tmp;
            }
        }
    }
}
     */

    /* 验证栈队列

    class Solution {
        public boolean validateStackSequences(int[] pushed, int[] popped) {
            Stack<Integer> stack = new Stack<>();
            int j = 0;
            for (int i = 0; i < pushed.length; i++) {
                stack.push(pushed[i]);
                while (!stack.empty() &&stack.peek() == popped[j]&&j < popped.length){
                    stack.pop();
                    j++;
                }
            }
            return stack.empty();
        }
    }

    */